1. Field of the Invention
The field of the invention is that of switched networks comprising a plurality of nodes connected by a plurality of physical communications links. These links generally provide for two-way data transfers, for example according to the IEEE 1355 standard.
More specifically, the present invention relates to the broadcasting of digital data packets, known as broadcast packets, within a switched network of this kind.
The invention can be applied especially but not exclusively to a high bit rate switched network comprising a small number of nodes used for the real-time exchange of moving pictures, for example for distribution within a dwelling.
Conventionally, each node of a switched network comprises a switch apparatus (sometimes also called a switch device hereinafter in the description) and a data-processing apparatus. The switch apparatus itself has a data packet routing device and an interface device between the routing means and the links.
Two types of data packets are generally distinguished. These are unicast packets and broadcast packets.
Whatever their type, data packets have a predetermined format comprising for example a routing header, a payload (containing useful data) and an end-of-packet or end-of-message indicator. A message consists of at least two packets or only one packet (in the latter case, the end-of-message indicator is used).
The path that a packet must take to reach its destination is determined by the sender (the routing is done at the source). This path is indicated in the header of the packet and is used by the intermediate nodes to determine the link along which the packet should be sent. It may be recalled that each packet that is conveyed by a link connected to a node reaches an input port of this node and is switched to an output port of this node from where it goes out again, being conveyed by the above-mentioned link or another link.
A broadcast packet is distinguished from a unicast packet by the fact that its header has a broadcast packet indicator indicating that it has to be sent to each of the nodes of the network.
Conventionally, the broadcast packets are broadcast along a spanning tree of the network. This tree is computed as a function of the topology of the network. This tree defines those links, among all the links forming the mesh of the network, that have to be used for the broadcasting of a broadcast packet from a source node to all the other nodes of the network. Indeed, each node that receives the broadcast packet must send it to one or more other nodes respectively through one or more links belong to the spanning tree.
2. Description of the Prior Art
There are mainly two known techniques by which a node can send a broadcast packet on several links of the spanning tree to several other nodes.
The first known technique consists of the duplication of the broadcast packet within the network into as many copies as there are links concerned by the broadcast at output of this node. In this way, the broadcast packet is sent independently (and therefore not simultaneously) on each of the links concerned.
Unfortunately, owing to the packet duplication mechanism that it requires, this first approach is very costly, at each node, in terms of processing and memory resources.
A second known technique has therefore been proposed. In this technique, the node sends the broadcast packet simultaneously on all the concerned links of the spanning tree. Thus, the costly implementation of the mechanism of duplicating packets within the node is avoided.
Hereinafter in the description, it is assumed that each node of the switched network is of the type implementing this second known technique (the sending of one and the same broadcast packet simultaneously on several links).
Traditionally, the spanning tree calculation techniques rely on an approach seeking to minimize the total “cost” of the links belonging to this tree. The term “cost of a link” is understood to mean especially the relative occupancy rate (or load rate) of this link with unicast traffic. The algorithms implemented in these standard spanning tree calculation techniques are well known to those skilled in the art and are, for example, described in the following document: Dimitri Bertsekas, Robert Gallager, “Data Networks”, 2nd Edition, Prentice-Hall International, 1992, ISBN 0-13-201674-5 (pages 390–393).
These conventional spanning tree calculation techniques turn out to have several drawbacks when each node of the switched network is of the type implementing the second known technique mentioned here above.
Indeed, when a node has to simultaneously send a broadcast packet on several links belonging to the spanning tree, it may happen that all these links are not simultaneously free. In other words, in the node, the output ports connected to certain links are not available. For example, one or more links may be in the course of being used for the sending of unicast packets. In this situation, the broadcast packet is blocked until all the links concerned by the broadcast become simultaneously free. The major drawback of this blocking is that it leads to an increase in the mean latency of broadcasting of a broadcast packet within the network.
Since they are optimized solely in terms of total load of the links, the conventional spanning tree calculation techniques do not take account of this problem of broadcasting congestion of the network.
It is an object of the invention especially to overcome this major drawback of the prior art.
More specifically, one of the goals of the present invention is to provide a method for the broadcasting of data packets, used to limit the mean latency of broadcast of a broadcast packet within the switched network.
It is also a goal of the invention to provide a method of this kind that is simple to implement and costs little.